package cn.chen.算法.排序;

import java.text.SimpleDateFormat;
import java.util.Arrays;
import java.util.Date;

/**
 * 快速排序：确定一个值，将数据分成两部分，一部分数据比另一部分数据大或者小，找到该值的确定位置。再将每一部分都分成两部分
 * */
public class QuickSort {

    public static void main(String[] args){

//        int[] a={9,4,5,-1,2,96,5};
        int []a=new int[80000];
        for(int i=0;i<a.length;i++){

            a[i]= (int) (Math.random()*800000);
        }
        SimpleDateFormat format=new SimpleDateFormat("yyyy-MM-dd hh:mm:ss");
        String start = format.format(new Date());
        System.out.println("开始时间："+start);

        quickSort(a,0,a.length-1);

        String end = format.format(new Date());
        System.out.println("结束时间："+end);
    }
    public static void quickSort(int[] a,int start,int end){

        if(start<end){

            int index = selectIndex(a, start, end); // 每次将数据分成两部分都需要找到该值的一个正确位置的索引
            quickSort(a,start,index-1);   // 循环将前面一组数据进行操作：找到确定值 然后确定值前为一组 确定值后为一组
            quickSort(a,index+1,end);
        }
    }
    public static int selectIndex(int [] a,int start,int end){

        // 该方法的作用就是找到该值的正确位置，并且将该值前后的大小弄为一致
        int num=a[start];   // 记录下该值，后面有用,
        while(start<end){   // 只要start<end 就一直循环

            while(start<end&&a[end]>=num)   // 先比较后面的，因为前面的第一个位置已经空出来了
                end--;
            a[start]=a[end];    // 循环结束了，所以end应该往前面赋值了，end的位置就要空出来了
            while (start<end&&a[start]<=num)
                start++;
            a[end]=a[start];
        }
        a[start]=num;   // start就是num的正确的位置
        return start;
    }
}
